Geografia generalizada

Na teoria da complexidade computacional, generalizada a geografia é problema PSPACE-completo bem conhecido.

Introdução

Geography é um jogo infantil que é bom para uma longa viagem de carro, onde os jogadores revezam entre si dizendo o nome de cidades ao redor do mundo. Cada cidade escolhida deve começar com a mesma letra que terminou o nome da cidade anterior. Repetição não é permitida. O jogo começa com uma cidade arbitrário e termina quando um jogador perde porque ele ou ela é incapaz de continuar.

Gráfico modelo

Para visualizar o jogo, um gráfico direcionado pode ser construído cujos nós são cidades do mundo. Uma seta é adicionada a partir do nó N₁ para o nó N₂ se, e somente se, a cidade com rotulagem N₂ começa com a letra que termina o nome da cidade com rotulagem N₁. Em outras palavras, vamos desenhar uma seta de uma cidade para outra se a primeira pode levar para a segunda de acordo com as regras do jogo. Cada aresta alternativa no gráfico direcionado corresponde a cada jogador (para um jogo de dois jogadores). O primeiro jogador incapaz de estender o caminho perde. Uma ilustração do jogo (contendo algumas cidades no estado de Michigan) é mostrado na figura abaixo.

Num jogo de geografia generalizada (GG), podemos substituir o gráfico de nomes de cidades com um grafo direcionado arbitrário. O gráfico a seguir é um exemplo de um simples jogo de geografia.

Jogando o jogo

Definimos P₁ como o jogador que se move de primeira e P₂ como o jogador de segundo e nomeamos os nós de N₁ a N_n. Na figura acima, P₁ tem uma estratégia vencedora, conforme segue: N₁ aponta apenas para os nós de N₂ e N₃. Assim, o primeiro movimento de P₁ deve ser uma dessas duas opções. P₁ escolhe N₂ (se P₁ escolher N₃, P₂ vai escolher N₉ já que é a única opção e P₁ vai perder). Em seguida P₂ escolhe N₄ porque é a única escolha remanescente. P₁ agora escolhe N₅ e P₂ , posteriormente, escolhe N₃ ou N₇. Independentemente da escolha de P₂, P₁ escolhe N₉ e P₂ não tem opções restantes e perde o jogo.

Declaração do problema

O problema de determinar qual jogador tem uma estratégia vencedora em um simples jogo de geografia é PSPACE-completo. Suponha que

GG = { <G, b> | P₁ tem uma estratégia vencedora para o jogo de geografia generalizada jogado no gráfico de G começando pelo nó b }.

Prova

Geografia generalizada está em PSPACE

Para mostrar que GG ∈ PSPACE, apresentamos um algoritmo recursivo de espaço polinomial que determina qual jogador tem uma estratégia vencedora. Dada uma instância de GG, <G, n_iniciar> onde G é um gráfico direcionado e n_iniciar é o ínicio nó, o algoritmo de M continua da seguinte maneira:

Em M(<G, n_iniciar>):

Medir o grau do nó n_iniciar. Se este grau é 0 e, em seguida, retornar rejeitar, porque não há movimentos disponíveis para o jogador.
Construir uma lista de todos os nós, acessível a partir de n_iniciar por uma borda: n₁, n₂, ..., nj.
Remova n_iniciar e todas as extremidades ligadas a ele a partir de G para formar G1.
Para cada nó n_j na lista n₁, ..., n_i, chamada de M(<G1, nj>).
Se todas estas chamadas retornarem aceitar, então não importa que decisão P₁ tome, P₂ tem uma estratégia para vencer, daí retorna rejeitar. Caso contrário (se uma das chamadas retornar rejeitar) P₁ tem uma escolha que vai negar qualquer estratégia bem sucedida para P₂, então retorna aceitar.

O algoritmo M claramente decide GG. É em PSPACE, porque é o único local de trabalho polinomial não óbvio consumido na pilha de recursão. O espaço consumido pelo pilha de recursão é polinomial porque cada nível de recursão adiciona um único nó para a pilha, e há, no máximo, n níveis, onde n é o número de nós em G.

Geografia generalizada é PSPACE-díficil

Para estabelecer o PSPACE-forte de GG, pode-se reduzir o problema do Jogo de fórmula (que é conhecido por ser PSPACE-forte) para GG em tempo polinomial (P). Em resumo, uma instância do problema do Jogo de fórmula consiste em um fórmula Booleana quantificada φ = ∃x₁ ∀x₂ ∃x₃ ...Qx_k(ψ) onde Q é ∃ ou ∀. O jogo é jogado por dois jogadores, o P_a e P_e, que alternam na escolha de valores sucessivos de x_i. P_e ganha o jogo se a fórmula ψ acaba sendo verdadeira, e P_um ganha, se ψ acaba falsa. A fórmula ψ é assumida estar na forma normal conjuntiva.

Nesta prova, assumimos que a lista quantificadora começa e termina com o qualificador existencial, ∃, para manter a simplicidade. Observe que qualquer expressão pode ser convertida para este formulário, adicionando variáveis de enchimento que não aparecem em ψ.

Através da construção de um grafo G como o mostrado acima, vamos mostrar qualquer instância do problema do Jogo de fórmula pode ser reduzida a uma instância de Geografia Generalizada, onde a melhor estratégia de P₁ é equivalente ao de P_e, e a melhor estratégia para P₂ é equivalente ao de Pa.

A cadeia vertical na esquerda dos nós foi projetada para imitar o procedimento de escolha de valores para as variáveis no Jogo de Fórmula. Cada estrutura de diamante corresponde a uma variável quantificada. Os jogadores revezam entre si para decidir caminhos em cada nó da ramificação. Já que assumimos que o primeiro quantificador seria existencial, P₁ vai primeiro, selecionando a esquerda do nó se x₁ é verdadeiro e o direito nó se x₁ é falso. Cada jogador deve, então, ter turnos forçados e, em seguida, P₂ escolhe um valor para x₂. Estas atribuições se alternando continuam para o lado esquerdo. Depois que ambos os jogadores passam por todos os diamantes, é novamente a vez de P₁, já que partimos do pressuposto de que o último quantificador é existencial. P₁ não tem escolha, a não ser seguir o caminho para o lado direito do gráfico. Em seguida, é a vez de P₂ fazer um movimento.

Quando o jogo chega no lado direito do grafo, é semelhante ao fim do jogo no jogo da fórmula. Lembre-se que o jogo da fórmula, P_e ganha se ψ é verdadeiro, enquanto que Pa ganha se ψ é falso. O lado direito do grafo garante que P₁ seja vitorioso se, e somente se, P_e vencer, e que P₂ vence se e somente se Pa vencer.

Primeiro vamos mostrar que P₂ sempre ganha quando Pa ganha. Se Pa ganhar, ψ é falso. Se ψ é falso, não existe uma cláusula insatisfatória. P₂ escolherá uma cláusula insatisfatória para ganhar. Em seguida, quando for a vez de P₁, ele deve escolher um literal na cláusula escolhida por P₂. Já que todos os literais da cláusula são falsos, eles não se conectam aos nós visitados anteriormente na cadeia vertical esquerda. Isso permite que P₂ siga a conexão até o nó correspondente num diamante da cadeia esquerda, e selecione-a. No entanto, o P₁ agora é incapaz de selecionar um nó adjacente e perde.

Agora vamos mostrar que P₁ sempre ganha quando P_e vence. Se P_e vence, ψ é verdadeiro. Se ψ é verdade, cada cláusula no lado direito do gráfico contém um literal verdadeiro. P₂ pode escolher qualquer cláusula. Então P₁ escolhe o literal que é verdadeiro. E porque ele é verdadeiro, o seu nó adjacente na vertical esquerda já foi selecionado, então P₂ não tem movimentos para fazer e perde.

Consequências

Dado que a GG é PSPACE-completo, nenhum algoritmo de tempo polinomial existe para um ótimo jogo no GG, a menos que P = PSPACE. No entanto, pode não ser tão fácil provar a complexidade de outros jogos, porque alguns jogos (como o xadrez) contém um número finito de jogo de posições — o que torna difícil (ou impossível) para formular um mapeamento para um problema PSPACE-completo. Apesar disso, a complexidade de alguns jogos podem ainda ser analisadas por generalização (por exemplo, para um tabuleiro n × n). Veja as referências para uma prova generalizada Go, como um corolário da prova da completude do GG.

Bibliografia

Michael Sipser, Introduction to the Theory of Computation, PWS, 1997.
David Lichtenstein and Michael Sipser, GO is polynomial Space Hard, Journal of the Association for Computing Machinery, April 1980.